Search for: All records

Confining materials to two-dimensional forms changes the behaviour of the electrons and enables the creation of new devices. However, most materials are challenging to produce as uniform, thin crystals. Here we present a synthesis approach where thin crystals are grown in a nanoscale mould defined by atomically flat van der Waals (vdW) materials. By heating and compressing bismuth in a vdW mould made of hexagonal boron nitride, we grow ultraflat bismuth crystals less than 10 nm thick. Due to quantum confinement, the bismuth bulk states are gapped, isolating intrinsic Rashba surface states for transport studies. The vdW-moulded bismuth shows exceptional electronic transport, enabling the observation of Shubnikov–de Haas quantum oscillations originating from the (111) surface state Landau levels. By measuring the gate-dependent magnetoresistance, we observe multi-carrier quantum oscillations and Landau level splitting, with features originating from both the top and bottom surfaces. Our vdW mould growth technique establishes a platform for electronic studies and control of bismuth’s Rashba surface states and topological boundary modes1,2,3. Beyond bismuth, the vdW-moulding approach provides a low-cost way to synthesize ultrathin crystals and directly integrate them into a vdW heterostructure. 

In this paper we study the fundamental problems of maximizing a continuous nonmonotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the first 1 2 -approximation algorithm for continuous submodular function maximization; this approximation factor of 1 2 is the best possible for algorithms that only query the objective function at polynomially many points. For the special case of DR-submodular maximization, i.e. when the submodular function is also coordinate-wise concave along all coordinates, we provide a different 1 2 -approximation algorithm that runs in quasi-linear time. Both these results improve upon prior work (Bian et al., 2017a,b; Soma and Yoshida, 2017). Our first algorithm uses novel ideas such as reducing the guaranteed approximation problem to analyzing a zero-sum game for each coordinate, and incorporates the geometry of this zero-sum game to fix the value at this coordinate. Our second algorithm exploits coordinate-wise concavity to identify a monotone equilibrium condition sufficient for getting the required approximation guarantee, and hunts for the equilibrium point using binary search. We further run experiments to verify the performance of our proposed algorithms in related machine learning applications. 

We study the problem of computing and learning non-anonymous reserve prices to maximize revenue. We first define the M aximizing M ultiple R eserves (MMR) problem in single-parameter matroid environments, where the input is m valuation profiles v 1 ,…, v m , indexed by the same n bidders, and the goal is to compute the vector r of (non-anonymous) reserve prices that maximizes the total revenue obtained on these profiles by the VCG mechanism with reserves r . We prove that the problem is APX -hard, even in the special case of single-item environments, and give a polynomial-time 1/2-approximation algorithm for it in arbitrary matroid environments. We then consider the online no-regret learning problem and show how to exploit the special structure of the MMR problem to translate our offline approximation algorithm into an online learning algorithm that achieves asymptotically time-averaged revenue at least 1/2 times that of the best fixed reserve prices in hindsight. On the negative side, we show that, quite generally, computational hardness for the offline optimization problem translates to computational hardness for obtaining vanishing time-averaged regret. Thus, our hardness result for the MMR problem implies that computationally efficient online learning requires approximation, even in the special case of single-item auction environments. 

This paper considers the problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. The main result is the first 1/2-approximation algorithm for continuous submodular function maximization; this approximation factor of 1/2 is the best possible for algorithms that only query the objective function at polynomially many points. For the special case of DR-submodular maximization, i.e. when the submodular functions are also coordinate-wise concave along all coordinates, we provide a different 1 2-approximation algorithm that runs in quasi-linear time. 

This paper considers a basic problem at the interface of submodular optimization and online learning. In the online unconstrained submodular maximization problem, there is a universe [n] = {1, 2, . . . , n} and a sequence of T nonnegative (not necessarily monotone) submodular functions arrive over time. The goal is to design a computationally efficient online algorithm, which chooses a subset of [n] at each time step as a function only of the past, such that the accumulated value of the chosen subsets is as close as possible to the maximum total value of a fixed subset in hindsight. Our main result is a polynomial time no-1/2-regret algorithm for this problem, meaning that for every sequence of nonnegative submodular functions, the algorithm’s expected total value is at least 1/2 times that of the best subset in hindsight, up to an error term sublinear in T. The factor of 1/2 cannot be improved upon by any polynomial-time online algorithm when the submodular functions are presented as value oracles. 

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players, Bob, his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result each time before the next piece is revealed to Bob. This model has a closer and more natural correspondence to dynamic data structures than classic communication models do, and hence presents a new perspective on data structures. We first present a tight lower bound for the online set intersection problem in the online communication model, demonstrating a general approach for proving online communication lower bounds. The online communication model prevents a batching trick that classic communication complexity allows, and yields a stronger lower bound. We then apply the online communication model to prove data structure lower bounds for two dynamic data structure problems: the Group Range problem and the Dynamic Connectivity problem for forests. Both of the problems admit a worst case O(logn)-time data structure. Using online communication complexity, we prove a tight cell-probe lower bound for each: spending o(logn) (even amortized) time per operation results in at best an exp(−δ2 n) probability of correctly answering a (1/2+δ)-fraction of the n queries.